The cheaper a resource becomes, the more important it becomes to have automatic management of that resource in a principled fashion. This is because the increased capacity makes it possible to apply that resource to lower-value uses. When a resource is expensive, all uses, in order to be worth the amount they consume, must exceed some minimum value to their users, so all uses of an expensive resource have high and comparable values. Also, because individual uses of an expensive resource have high value, it is both easy and worthwhile to manage the resource manually. When the price per unit of that resource drops by multiple orders of magnitude, uses that have a low value per resource unit become feasible, but these low-value uses can crowd out the high-value uses if there is no way to express the value differences--and manual management of the resource becomes prohibitively difficult, as well as expensive relative to the value of the resource.
For example, the transition to fiber data communication makes possible bandwidth-intensive applications like video. It might seem, since fiber has so much more bandwidth than previous communications media, that existing network allocation policies (like those used in Ethernet) can simply be scaled. However, in the case of Ethernet, the amount of bandwidth that an application is allocated is proportional to how much it asks for and how often it asks. In such a regime, network users trying to transmit, for example, electronic mail may find network performance significantly reduced by the presence of video users, even though both the data users and video users would agree that the value per bit of electronic mail is far higher than that of video data: a megabyte of capacity would carry an entire day's correspondence for a large company, but amount to only a single frame of high-resolution video, which the video user could drop without noticing. Expanding the overall capacity of the network will not address the problem, because the higher capacity of the network invites still more video use. Non-agoric protocols provide no way to express this value difference. Thus, economic abstractions, such as price and value, meaningful to the system and automatically taken into account, are needed in order to manage abundant computing resources.
The primary existing resource allocation methods for allocating a computer system resource are: (1) first come first served, (2) priority based allocation methods, (3) pro rata allocation methods (allocate in proportion to amount requested), and (4) simple "single good" auction methods. In "first come first served" systems, bandwidth is assigned in the order that requests are made, until there is insufficient bandwidth left to satisfy further requests, at which point the requests that cannot be satisfied are simply denied. In priority based allocation methods, higher priority requests displace lower priority requests when there is insufficient bandwidth to satisfy all requests.
For systems having a single allocatable system resource (such as bandwidth on a transmission medium) and many requesters, such as the system shown in FIG. 1, the prior art literature discloses a technique that will for the purposes of this document be called "single good auctions." In a single good auction, each requester specifies the amount of the good being requested, and a bid price that the requester is willing to pay. The arbiter (sometimes called the auctioneer) selects the set of bids that maximize the payment received, and each successful requester whose request is granted pays the amount that the requester bid.
There are several different ways in which such single good auctions can be conducted. Conventional auction techniques include the English auction, also known as the first-price, open-bid auction, in which the highest price bid is the price paid and every bidder knows the bids made by others. Another auction mechanism is the Dutch auction, in which a seller offers lower and lower prices until a buyer or set of buyers claims the item at the last offered price. In a double auction, sellers offer lower and lower prices while buyers offer higher and higher prices until they meet. In a first-price sealed-bid auction, fixed bids are submitted and the highest is accepted. In a second-price sealed-bid auction, the highest bid is accepted, but the highest bidder pays the amount bid by the second-highest bidder.
While the prior art has provided many well proven systems for allocating a single resource through various auction and arbitration systems, those systems are not appropriate for the simultaneous arbitration of multiple goods, or "baskets of goods," where the goods being allocated are relatively inexpensive and in such great supply that the requests of numerous requesters can be satisfied simultaneously. For instance, one might think that each of the goods could be allocated separately through a separate arbitration, using one of the known arbitration mechanisms. However, the inadequacy of separate arbitrations is demonstrated as follows. A user who requests 8 Mb/sec of bandwidth on three sequentially connected links needs to be allocated exactly the same amount of bandwidth on all three links, or none at all. Allocating this user 8 Mb/sec of bandwidth on two of the links and none on the third link is of zero value to the user, because without a bandwidth allocation on the third link he will receive no signals whatsoever.
Thus, it is an object of the present invention to provide a diverse goods arbitration mechanism that preserves the integrity of each diverse goods bid and either allocates all the goods in a bid, in the quantities requested, or denies the bid.
Another object of the present invention is to provide an efficient and fair system and method for allocating a plurality of computer resources in an integrated arbitration, and for allocating costs to the successful requesters in accordance with the opportunity costs associated with each successful request for computer resources.